#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstdint>
#include <ctime>
#include <stack>
#include <string>

using namespace std;

class Solution {
public:
    vector<int> test;
    int trap(vector<int>& height) {
        stack<int> sta;
        int water = 0;
        int state = 0;
        int popValue;
        for (int i = 0; i < height.size(); i++){
            if (sta.empty()){ //build the left boundary
                sta.push(i);
                state = 0;
                continue;
            }
            switch (state) {
            case 0:
                if (height[i] < height[sta.top()]){//save water
                    sta.push(i);
                    state++;
                }else{ //more higher edge, replace the left boundary
                    sta.pop();
                    sta.push(i);
                }
                break;
            case 1:
                if (height[i] > height[sta.top()]){ //find the right boundary
                    while(!sta.empty()){ //find the left boundary
                        if (height[i] > height[sta.top()]){
                            popValue = height[sta.top()];
                            sta.pop();
                            if (sta.empty()){
                                sta.push(i);
                                state = 0;
                                break;
                            }else{
                                water += (i - sta.top() - 1) * (min(height[i], height[sta.top()]) - popValue); //get water
                                printf("i is %d, sta.top() is %d, water is %d\r\n", \
                                       i, sta.top(), water);
                            }
                        }else{
                            sta.push(i);
//                            state = 0;
                            break;
                        }
                    }
                }else{
                    sta.push(i); //save water
                }
                break;
            default:
                break;
            }
        }
        return water;
    }
};

int main()
{
    Solution su;
//    su.test = {0,1,0,2,1,0,1,3,2,1,2,1};
//    su.test = {2,1,0,2};
    su.test = {2,0,2};
    int result = su.trap(su.test);
    printf("the result is %d\r\n", result);
    return 0;
}
